//两数之和 II - 输入有序数组
/*给定一个已按照 升序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。*/
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0;
        int right = numbers.size() - 1;
        vector<int> ret(2);
        while (left < right) {
            if (numbers[left] + numbers[right] > target) {
                right--;

            } else if (numbers[left] + numbers[right] < target) {
                left++;
            } else {
                ret[0] = left;
                ret[1] = right;
                break;
            }
        }
        return ret;
    }
};


//数组中出现次数超过一半的数字
/*给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
*/
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型vector
     * @return int整型
     */
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        // write code here
        int cand = numbers[0];
        int count = 1;
        for (int i = 1; i < numbers.size(); i++) {
            if (count == 0) {
                cand = numbers[i];
            }
            if (numbers[i] != cand) {
                count--;
            } else {
                count++;
            }
        }
        return cand;
    }
};